package Algorithm.search;

import java.util.Arrays;

/**
 * 判断一个ip是否在一系列IP段内
 * 题目简述：给定一组不重叠的ip段，判断一个ip是否在其中某个ip段内
 */
public class IsInIpPairs {


    /**
     * 思路：首先将ip都转换为long类型整数，对ip区间进行排序，然后在这n个有序的整数区间中进行二分查找，
     * 这里就可以领会二分查找的本质，不仅是单纯的有序序列可以二分，有序区间也可以二分
     */
    public static boolean isInIpPairs(String[][] ipPairs, String ip) {
        int n = ipPairs.length;
        long[][] longIpPairs = new long[n][2];
        for (int i = 0;i < n;i++) {
            longIpPairs[i][0] = ipToLong(ipPairs[i][0]);
            longIpPairs[i][1] = ipToLong(ipPairs[i][1]);
        }
        Arrays.sort(longIpPairs, (p1, p2) -> p1[0] - p2[0] < 0 ? -1 : 1);
        long target = ipToLong(ip);
        int low = 0, high = n-1; //在n个有序区间中进行二分查找
        while (low <= high) {
            int mid = low + high >> 1;
            if (longIpPairs[mid][0] <= target && longIpPairs[mid][1] >= target) //命中区间则直接返回，否则在左半部分或右半部分查找
                return true;
            else if (longIpPairs[mid][0] > target) high = mid - 1;
            else low = mid + 1;
        }
        return false;
    }

    /**
     * ip为32位二进制整数，可用long类型表示，用int可能会溢出为负数
     */
    public static long ipToLong(String ip) {
        String[] ss = ip.split("\\."); //注意在split特殊字符时要进行转义
        long result = 0;
        for (int i = 0;i < 4;i++) {
            long num = Long.parseLong(ss[i]);
            result += num << 8*(3-i); //通过右移8位统计每部分的值
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(ipToLong("255.255.255.255"));
        System.out.println(isInIpPairs(new String[][]{{"255.1.255.255","255.255.255.222"},{"123.255.255.255", "175.255.255.212"}}, "255.255.255.221"));
    }
}
